package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author By ZengPeng
 */
public class 力扣_994_腐烂的橘子 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_994_腐烂的橘子().orangesRotting(new int[][]{{1},{2}}));
//        System.out.println(new 力扣_994_腐烂的橘子().orangesRotting(new int[][]{{2,1,1},{1,1,0},{0,1,1}}));//4
//        System.out.println(new 力扣_994_腐烂的橘子().orangesRotting(new int[][]{{2,1,1},{0,1,1},{1,0,1}}));//-1
//        System.out.println(new 力扣_994_腐烂的橘子().orangesRotting(new int[][]{{0}}));//0
//        System.out.println(new 力扣_994_腐烂的橘子().orangesRotting(new int[][]{{1,2}}));//1    //58
//        System.out.println(new 力扣_994_腐烂的橘子().orangesRotting(new int[][]{{2,0,1,1,1,1,1,1,1,1},{1,0,1,0,0,0,0,0,0,1},{1,0,1,0,1,1,1,1,0,1},{1,0,1,0,1,0,0,1,0,1},{1,0,1,0,1,0,0,1,0,1},{1,0,1,0,1,1,0,1,0,1},{1,0,1,0,0,0,0,1,0,1},{1,0,1,1,1,1,1,1,0,1},{1,0,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}}));
    }

    /**
    题目：在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
     值 0 代表空单元格；
     值 1 代表新鲜橘子；
     值 2 代表腐烂的橘子。
     每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
     返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

     示例 1：
     输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
     输出：4

     示例 2：
     输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
     输出：-1
     解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

     示例 3：
     输入：grid = [[0,2]]
     输出：0
     解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

    分析：【PR ❤🧡💛💙💚】
       1.深度优先遍历【动态规划 + 回溯】：找到烂橘子，从烂橘子开始向下递归。找到新鲜橘子感染，否则返回
            --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
       2.广度优先遍历: 层层扫描记录节点,找到烂橘子,将附近的节点放进扫描数组，腐烂时间+1
            【我是一个个小圈扫描】，并记录了腐烂时间，再度扫描到时，会比较腐烂时间大小
            --执行用时：2 ms, 在所有 Java 提交中击败了40.84%的用户
       3.广度优先遍历【大佬优化】：只记录扫描次数，而不是记录每个橘子的腐烂时间，每次将新感染的橘子加入队列，并直接视为烂橘子
            【大佬是一个大圈的扫描】
            --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1. 如果有橘子是-1，则永远不会烂完
       2.[[0]]  ,空篮子 预期结果0！！ 因为题目说的没有新鲜橘子为止   =0
       3.[[1,2]] ,判断Math.min前，要看看自己是否是-1   1
       4.[[1],[2]]
     **/
    public int orangesRotting(int[][] grid) {
        //2.1【大佬】广度优先遍历: 层层扫描记录节点,找到烂橘子,将附近的节点放进扫描数组，腐烂时间+1
        Queue<int[]> queue = new LinkedList<>();
        int m = grid.length;
        int n = grid[m-1].length;
        int count = 0;
        for (int i = 0 ; i < m ; i ++){
            for(int j = 0 ; j < n ; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i,j}); //找到所有烂橘子坐标
                } else if (grid[i][j] == 1) {
                    count++;//记录新鲜橘子个数
                }
            }
        }
        int minute = -1;
        int[][] xy = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};  //四个方向的横纵坐标点变化
        while (!queue.isEmpty()) {
            int size = queue.size();
            for(int b = 0 ; b < size ; b++){//【巧妙的方法，只把上一层的橘子遍历出来】
                int[] point = queue.poll();
                int x = point[0],y = point[1];
                for (int a = 0; a < xy.length; a++) {
                    int newX = x + xy[a][0];
                    int newY = y + xy[a][1];
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {//【新鲜橘子被感染，数量减1】
                        grid[newX][newY] = 2;//直接是为烂橘子，避免重复判断
                        queue.offer(new int[]{newX, newY});
                        count--;
                    }
                }
            }
            minute++;//每感染一轮的时间+1
        }
        if(count > 0)//如果还有新鲜橘子，说明未被感染，返回-1
            return -1;
        return minute == -1 ? 0 : minute;

        // 2.广度优先遍历: 层层扫描记录节点,找到烂橘子,将附近的节点放进扫描数组，腐烂时间+1
        /*int[][] res = new int[grid.length][grid[0].length];//默认都是0。如果是腐烂橘子0.如果是新鲜橘子判断是否为0？ -1：max
        Deque<int[]> deque = new ArrayDeque<>();//记录当前的新鲜橘子
        int[][] point = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};  //四个方向的横纵坐标点变化
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++) {
                if (grid[x][y] == 2) {//找到烂橘子，以此为起点
                    deque.add(new int[]{x, y});
                    while (!deque.isEmpty()) {
                        int[] current = deque.poll();
                        int path = res[current[0]][current[1]] + 1;
                        for (int[] aPoint : point) {
                            int newX = current[0] + aPoint[0];
                            int newY = current[1] + aPoint[1];
                            if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length
                                    && grid[newX][newY] == 1 && (res[newX][newY] == 0 || res[newX][newY] > path)) {
                                deque.add(new int[]{newX, newY});
                                res[newX][newY] = path;
                            }
                        }
                    }
                }
            }
        }
        int max=0;
        for (int x = 0; x < grid.length; x++) {//遍历每个橘子的腐烂时间
            for (int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 1){
                    if(res[x][y]==0) return -1;
                    max = Math.max(max,res[x][y]);
                }
            }
        }
        return max;*/
    }

    public int orangesRotting0(int[][] grid) {
        //1.深度优先遍历【动态规划 + 回溯】：找到烂橘子，从烂橘子开始向下递归。找到新鲜橘子感染，否则返回
        int[][] res = new int[grid.length][grid[0].length];
        for (int x = 0; x < grid.length; x++) {//初始化所有格子，默认都是-1 永不腐烂
            for (int y = 0; y < grid[0].length; y++)
                res[x][y] = -1;
        }
        boolean[][] isUsed = new boolean[grid.length][grid[0].length];
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++)
                if(grid[x][y]==2){//找到烂橘子，以此为起点
                    res[x][y]=0;
                    bfs(grid,x-1,y,1,res,isUsed);//遍历附近的好橘子，计算感染时间
                    bfs(grid,x+1,y,1,res,isUsed);
                    bfs(grid,x,y-1,1,res,isUsed);
                    bfs(grid,x,y+1,1,res,isUsed);
                }
        }
        int max=0;
        for (int x = 0; x < grid.length; x++) {//遍历每个橘子的腐烂时间
            for (int y = 0; y < grid[0].length; y++)
                if(grid[x][y] != 0){
                    if(res[x][y]==-1) return -1;
                    max = Math.max(max,res[x][y]);
                }
        }
        return max;
    }


    private void bfs(int[][] grid, int x, int y,int day, int[][] res, boolean[][] isUsed) {
        if(x<0||x>=grid.length || y<0 || y>=grid[0].length || isUsed[x][y] || grid[x][y]!=1)
            return;
        if(res[x][y]!=-1 && day>=res[x][y])
            return;
        isUsed[x][y] = true;
        res[x][y]=day;
        bfs(grid,x-1,y,day+1,res,isUsed);
        bfs(grid,x+1,y,day+1,res,isUsed);
        bfs(grid,x,y-1,day+1,res,isUsed);
        bfs(grid,x,y+1,day+1,res,isUsed);
        isUsed[x][y] = false;
    }
}
